package com.example.algorithm.huawei_rongyao_29;

public class Q07_CardGameWinner02 {

    // 暴力尝试
    public static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
    }

    public static int f(int[] arr, int i, int j) {
        if (i == j) {
            return arr[i];
        }
        return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
    }

    public static int s(int[] arr, int i, int j) {
        if (i == j) {
            return 0;
        }
        return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
    }

    // 单独调用自己的暴力尝试
    public static int process(int[] arr, int i, int j) {
        if (i == j) {
            return arr[i];
        }
        if (i == j - 1) {
            return Math.max(arr[i], arr[j]);
        }
        return Math.max(arr[i] + Math.min(process(arr, i + 2, j), process(arr, i + 1, j - 1)),
                arr[j] + Math.min(process(arr, i + 1, j - 1), process(arr, i, j - 2))
        );
    }

    public static void main(String[] args) {
        int[] arr = {1, 9, 1};
        System.out.println(win1(arr));
    }
}
